Partition


How does the Quicksort partitioning algorithm work?

	1. swap pivot with last item
	2. repeat
	   run i from left to right
	   run j from right to left
	   stop i on large item
	   stop j on small item
	   if i and j not crossed, swap
	3. swap position i with pivot


Show each step of partition on the array.

	8 2 4 1 2 4



Items Equal to the Pivot


We can make the indexes i and j either stop or keep moving
when they encounter an item that is equal to the pivot.


What happens if i and j stop when the item is equal to the pivot?

	swap at each position when all keys equal
	pivot is placed in middle
	n log n time


What happens if i and j keep moving when the item is equal to the pivot?

	no swaps when all keys equal
	pivot is last item
	quadratic time



Median-of-three Partitioning


How can median-of-three pivot selection help with partitioning?

	put smallest of three in first position
	put largest of three in last position
	put median in middle
	1. swap middle with next-to-last item
	2. scan from low+1 and high-2
	   first/last items act as sentinels
	3. swap position i with next-to-last item


Show each step of median-of-three partitioning on the array.

	8 2 4 1 2 4



Small Arrays


Insertion Sort is faster than Quicksort for small arrays.
How can you use this fact to improve the Quicksort implementation?

	switch to insertion sort at size 10
	also avoids degenerate cases



    /**
     * Quicksort algorithm.
     * @param a an array of Comparable items.
     */
    public static void quicksort( Comparable [ ] a )
    {
        quicksort( a, 0, a.length - 1 );
    }

    private static final int CUTOFF = 10;

    /**
     * Method to swap to elements in an array.
     * @param a an array of objects.
     * @param index1 the index of the first object.
     * @param index2 the index of the second object.
     */
    public static final void swapReferences( Object [ ] a, int index1, int index2 )
    {
        Object tmp = a[ index1 ];
        a[ index1 ] = a[ index2 ];
        a[ index2 ] = tmp;
    }

    /**
     * Internal quicksort method that makes recursive calls.
     * Uses median-of-three partitioning and a cutoff of 10.
     * @param a an array of Comparable items.
     * @param low the left-most index of the subarray.
     * @param high the right-most index of the subarray.
     */
    private static void quicksort( Comparable [ ] a, int low, int high )
    {
        if( low + CUTOFF > high )
            insertionSort( a, low, high );
        else
        {
                // Sort low, middle, high
            int middle = ( low + high ) / 2;
            if( a[ middle ].compareTo( a[ low ] ) < 0 )
                swapReferences( a, low, middle );
            if( a[ high ].compareTo( a[ low ] ) < 0 )
                swapReferences( a, low, high );
            if( a[ high ].compareTo( a[ middle ] ) < 0 )
                swapReferences( a, middle, high );

                // Place pivot at position high - 1
            swapReferences( a, middle, high - 1 );
            Comparable pivot = a[ high - 1 ];

                // Begin partitioning
            int i, j;
            for( i = low, j = high - 1; ; )
            {
                while( a[ ++i ].compareTo( pivot ) < 0 )
                    ;
                while( pivot.compareTo( a[ --j ] ) < 0 )
                    ;
                if( i >= j )
                    break;
                swapReferences( a, i, j );
            }

                // Restore pivot
            swapReferences( a, i, high - 1 );

            quicksort( a, low, i - 1 );    // Sort small elements
            quicksort( a, i + 1, high );   // Sort large elements
        }
    }

    /**
     * Internal insertion sort routine for subarrays
     * that is used by quicksort.
     * @param a an array of Comparable items.
     * @param low the left-most index of the subarray.
     * @param n the number of items to sort.
     */
    private static void insertionSort( Comparable [ ] a, int low, int high )
    {
        for( int p = low + 1; p <= high; p++ )
        {
            Comparable tmp = a[ p ];
            int j;

            for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }